package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

public class MaximumSubarray {

    /**
     * 动态规划
     * 计算当前位置的最大子序和
     * dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
     *
     * @param nums 1 <= nums.length <= 3 * 104
     *             -10^5 <= nums[i] <= 10^5
     */
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < n; ++i){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            PrintUtils.println(dp);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int i = new MaximumSubarray().maxSubArray(nums);
        System.out.println(i);
    }

}
